package com.note.feng.leetcode.algorithms.easy.tree;

public class SevenHundred {
    /**
     * 700 二叉搜索树中的搜索
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     *
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     *
     * 示例 1:
     *
     * 输入：root = [4,2,7,1,3], val = 2
     * 输出：[2,1,3]
     * 示例 2:
     *
     * 输入：root = [4,2,7,1,3], val = 5
     * 输出：[]
     *  
     * 提示：
     *
     * 数中节点数在 [1, 5000] 范围内
     * 1 <= Node.val <= 107
     * root 是二叉搜索树
     * 1 <= val <= 107
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/search-in-a-binary-search-tree
     */
    /**
     * 解法：递归
     * 如果节点为空，直接返回空；如果不为空，判断节点的值是否与 val 一致，
     * 如果一致，直接返回，不一致：
     * 1、先遍历节点的左子树，若返回值不为空，直接返回，若为空，直接返回其右子树的遍历结果
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode left = searchBST(root.left, val);
        if(left != null){
            return left;
        }
        return searchBST(root.right, val);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
